package backtrack_or_fs.bfs_dfs;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;

/**
 * https://binarysearch.com/problems/Shortest-Cycle-Containing-Target-Node
 * 理解题意:
 *
 * 示例 1
 * 输入
 * graph = [
 *     [1],
 *     [2],
 *     [0]
 * ]
 * target = 0
 * 输入的解释:
 *
 * index=0的结点的邻接nodes数组是: [1],
 *
 * index=1的结点的邻接nodes数组是: [2],
 *
 * index=2的结点的邻接nodes数组是: [0]
 *
 * 输出
 * 3
 * 解释
 * 结点 0 -> 1 -> 2 -> 0 形成了一个环
 *
 * 示例 2
 * 输入
 * graph = [
 *     [1],
 *     [2],
 *     [4],
 *     [],
 *     [0]
 * ]
 * target = 3
 * 输入的解释:
 *
 * index=0的结点的邻接nodes数组是: [1],
 *
 * index=1的结点的邻接nodes数组是: [2],
 *
 * index=2的结点的邻接nodes数组是: [4],
 *
 * index=3的结点的邻接nodes数组是: [], 为空, 表示没与之连接的相邻结点。
 *
 * index=4的结点的邻接nodes数组是: [0]
 *
 * 输出
 * -1
 * 提示 #1
 * 试试从“目标”结点运行BFS广度优先搜索并记录“visited” set。
 */
class 求邻接矩阵中点所在环的最小长度 {

        // 步数统计型  每次记录queue.size() 最终求size
        // bfs图注意保留visited记录 避免死循环
        public int solve(int[][] graph, int target) {
            // from target,find next until target by bfs
            // save the steps, return steps first if find the target  or return -1 at the end
            // step incr in every round
            // graph第一维代表 当前是哪个点 ，第二维代表指向的点，可能指向很多点
            Queue<Integer> queue = new LinkedList<>();
            queue.offer(target);
            HashSet<Integer> visited = new HashSet<>();
            int step = 0;
            while(!queue.isEmpty()) {
                int size = queue.size();
                for(int i = 0; i< size; i++) {
                    int cur = queue.poll();
                    for(int node : graph[cur]) {
                        if(node == target) {
                            return step + 1;
                        }
                        if(!visited.contains(node)){
                            visited.add(node);
                            queue.offer(node);
                        }

                    }
                }
                step ++;
            }
            return -1;
        }
    }
